/*
    贪心经典题目专题5

    前置知识: 
    讲解005、042 - 对数器
    讲解025、026、027 - 基础排序、有序表、比较器、堆结构

    狭义的贪心
    每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法

    广义的贪心
    通过分析题目自身的特点和性质，只要发现让求解答案的过程得到加速的结论，都算广义的贪心

    贪心是最符合自然智慧的思想，一般分析门槛不高
    理解基本的排序、有序结构，有基本的逻辑思维就能理解
    但是贪心的题目，千题千面，极难把握
    难度在于证明局部最优可以得到全局最优，好在！我们有对数器！贪心专题2、3，这两节大量使用对数器

    ================================================

    有关贪心的若干现实 & 提醒
    1，不要去纠结严格证明，每个题都去追求严格证明，浪费时间、收益很低，而且千题千面。玄学！
    2，一定要掌握用对数器验证的技巧，这是解决贪心问题的关键
    3，解法几乎只包含贪心思路的题目，代码量都不大
    4，大量累积贪心的经验，重点不是证明，而是题目的特征，以及贪心方式的特征，做好总结方便借鉴
    5，关注题目数据量，题目的解可能来自贪心，也很可能不是，如果数据量允许，能不用贪心就不用（稳）
    6，贪心在笔试中出现概率不低，但是面试中出现概率较低，原因是 淘汰率 vs 区分度
    7，广义的贪心无所不在，可能和别的思路结合，一般都可以通过自然智慧想明白，依然不纠结证明

    ================================================

    题目1
    跳跃游戏II
    给定一个长度为n的整数数组nums
    你初始在0下标，nums[i]表示你可以从i下标往右跳的最大距离
    比如，nums[0] = 3
    表示你可以从0下标去往：1下标、2下标、3下标
    你达到i下标后，可以根据nums[i]的值继续往右跳
    返回你到达n-1下标的最少跳跃次数
    测试用例可以保证一定能到达
    测试链接 : https://leetcode.cn/problems/jump-game-ii/

    ================================================

    题目2
    灌溉花园的最少水龙头数目
    在x轴上有一个一维的花园，花园长度为n，从点0开始，到点n结束
    花园里总共有 n + 1 个水龙头，分别位于[0, 1, ... n]
    给你一个整数n和一个长度为n+1的整数数组ranges
    其中ranges[i]表示
    如果打开点i处的水龙头，可以灌溉的区域为[i-ranges[i], i+ranges[i]]
    请你返回可以灌溉整个花园的最少水龙头数目
    如果花园始终存在无法灌溉到的地方请你返回-1
    测试链接 : 
    https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/

    ================================================

    题目3
    字符串转化
    给出两个长度相同的字符串str1和str2
    请你帮忙判断字符串str1能不能在 零次 或 多次 转化后变成字符串str2
    每一次转化时，你可以将str1中出现的所有相同字母变成其他任何小写英文字母
    只有在字符串str1能够通过上述方式顺利转化为字符串str2时才能返回true
    测试链接 : https://leetcode.cn/problems/string-transforms-into-another-string/

    ================================================
    
    题目4
    过河问题
    一共n人出游，他们走到一条河的西岸，想要过河到东岸
    每个人都有一个渡河时间ti，西岸有一条船，一次最多乘坐两人
    如果船上有一个人，划到对岸的时间，等于这个人的渡河时间
    如果船上有两个人，划到对岸的时间，等于两个人的渡河时间的最大值
    返回最少要花费多少时间，才能使所有人都过河
    测试链接 : https://www.luogu.com.cn/problem/P1809

    ================================================

    题目5
    超级洗衣机
    假设有n台超级洗衣机放在同一排上
    开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的
    在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机
    与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机
    给定一个整数数组machines代表从左至右每台洗衣机中的衣物数量
    请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数
    如果不能使每台洗衣机中衣物的数量相等则返回-1
    测试链接 : https://leetcode.cn/problems/super-washing-machines/

*/